2621. Путь короля

Шахматы – это игра на квадратной доске из восьми строк и восьми столбцов. Столбцы нумеруются буквами от ‘a’ до ‘h’ слева направо, а строки нумеруются цифрами от ‘1’ до ‘8’ снизу вверх. Для игры в шахматы Вам следует понять правила, по которым ходят и атакуют фигуры. Одной из шахматных фигур является пешка. Пешка бьет по диагонали, на один квадрат вверх и влево или вправо. Например, если пешка находится на c3, то она угрожает полям d4 и b4. Другой шахматной фигурой является король. Король может двигаться или атаковать на один квадрат в любом направлении по вертикали, горизонтали или диагонали. Когда пешка (или король) атакует клетку, то она передвигается на нее и бьет фигуру, которая там находится.

Вам заданы начальные координаты короля, пешки A и пешки B. Найдите наименьшее количество ходов, за которое король сможет побить пешку A. Король не может ходить на поля, которые находятся под ударом пешек, а также не может выходить за пределы доски. Король может побить пешку B, однако делать это не обязательно. Пешкам передвигаться запрещено.

Вход. Состоит из нескольких тестов. Каждая строка описывает один тест и содержит начальное положение короля, пешки A и пешки B. Каждая позиция описывается двумя символами. Первый символ задает столбец (‘a’ – ‘h’), а второй символ задает строку (‘1’ – ‘8’). Все три позиции разные. Начальное положение короля не находится под ударом ни одной пешки.

Выход. Для каждого теста вывести в отдельной строке наименьшее количество ходов, за которое король сможет побить пешку A.

Пример входа	Пример выхода
c4 e6 d5 g2 a8 a2 a3 b1 c1	2 6 7

РЕШЕНИЕ

графы - поиск в ширину

Анализ алгоритма

Рассмотрим два варианта движения короля:

1. Король направляется к пешке А несмотря на положение пешки В и съедает ее;

2. Король направляется к пешке В, съедает ее и потом двигается к пешке А.

В обоих случаях при движении короля используется кратчайший путь, который находится поиском в ширину. Находим наименьшее количество ходов в первом и во втором случаях и возвращаем наименьшее среди них значение. Второй случай необходим, например, если изначально пешка А находится под ударом пешки B.

В поля, находящиеся под ударом пешек, изначально поставим значения 1000. Таким образом при поиске в ширину король на них не зайдет. Начальные положения короля и двух пешек занесем соответственно в переменные (kx, ky), (pax, pay), (pbx, pby). Запустим bfs(kx, ky). Занесем в переменные a и b наименьшее число ходов, которыми можно добраться до пешки А и В соответственно: a = m[pax][pay], b = m[pbx][pby]. Если пешка В сбивается, то следует запустить bfs(pbx, pby), найдя таким образом кратчайший путь от пешки В до А. Добавим к b значение m[pax][pay] после второго вызова bfs. Таким образом в a содержится длина кратчайшего пути короля до достижения цели без сбивания пешки В, а в b – со сбиванием. Вычисляем меньшее значение среди a и b.

Реализация алгоритма

Шахматную доску храним в массиве m. Очередь пар d используется для поиска в ширину и содержит координаты полей шахматной доски (x, y). Массивы xx и yy описывают возможные ходы короля: из клетки (i, j) король может пойти в любую из клеток (i + xx[k], j + yy[k]), где 1 ≤ k ≤ 8.

int m[10][10];

deque<pair<int,int> > d;

int xx[8] = {1, 1, 1, -1, -1, -1, 0, 0};

int yy[8] = {-1, 0, 1, -1, 0, 1, 1, -1};

Функция cango проверяет, не находится ли поле (x, y) за границами шахматной доски.

int cango(int x, int y)

{

if ((x < 1) || (x > 8) || (y < 1) || (y > 8) || (m[x][y] >= 0))

return 0;

return 1;

}

Функция bfs реализует поиск в ширину из клетки (x, y). С ее помощью ищем кратчайший путь короля до каждой из пешек.

void bfs(int x, int y)

{

m[x][y] = 0;

d.push_back(make_pair(x,y));

while(!d.empty())

{

pair<int,int> temp = d[0]; d.pop_front();

Перебираем все возможные ходы короля.

for(int i = 0; i < 8; i++)

{

int dx = temp.first + xx[i];

int dy = temp.second + yy[i];

if (cango(dx, dy))

{

m[dx][dy] = m[temp.first][temp.second] + 1;

d.push_back(make_pair(dx, dy));

}

}

}

}

Функция attackPawns возвращает наименьшее количество ходов, за которое король сможет побить пешку A.

int attackPawns(void)

{

memset(m,-1,sizeof(m));

В поля, находящиеся под ударом пешек, поставим значения 1000. Это делается для того, чтобы при поиске в ширину король в них не зашел.

m[pax-1][pay+1] = m[pax+1][pay+1] = 1000;

m[pbx-1][pby+1] = m[pbx+1][pby+1] = 1000;

bfs(kx,ky);

До пешки А король может добраться минимум за а ходов, а до пешки B за b ходов.

int a = m[pax][pay], b = m[pbx][pby];

memset(m,-1,sizeof(m));

m[pax-1][pay+1] = m[pax+1][pay+1] = 1000;

Вычисляем кратчайший путь от пешки В до пешки А.

bfs(pbx,pby); b += m[pax][pay];

В переменной a содержится длина кратчайшего пути короля до пешки A без сбивания пешки В, а в переменной b с ее сбиванием. Возвращаем меньшее значение среди a и b.

return (a < b) ? a : b;

}

Основная часть программы. Читаем входные данные. Находим и выводим ответ.

while(scanf("%c%c %c%c %c%c\n",&kx, &ky, &pax, &pay, &pbx, &pby) == 6)

{

kx -= 'a' - 1; ky -= '1' - 1; pax -= 'a' - 1; pay -= '1' - 1;

pbx -= 'a' - 1; pby -= '1' - 1;

res = attackPawns();

printf("%d\n",res);

}